package com.jn.algorithm.day014.question42;

import java.util.Arrays;

/**
 * @author 江南大学1033190417
 * @date 2022/4/29 20:43
 */
public class Solution {
    //暴力解法
    /*
    遍历当前右边的所有结点找到最大值，遍历当前右边所有的最大值
    去两个最大值的最小值作为高*1加大面积里面
     */
    public int trap(int[] height) {
        int ans = 0;
        int n = height.length;
        for (int i = 1; i < n - 1; i++) {
            //求左边的最大值
            int maxZuo = 0;
            for (int m = 0; m < i; m++) {
                maxZuo = Math.max(maxZuo, height[m]);
            }
            int maxYou = 0;
            for (int k = i + 1; k < n; k++) {
                maxYou = Math.max(maxYou, height[k]);
            }
            int area = Math.min(maxZuo, maxYou) - height[i];
            ans += Math.max(area, 0);
        }
        return ans;
    }

    //动态规划
    /*
    遍历数组
     */
    public int trap2(int[] height) {
        int n = height.length;
        int ans = 0;
        int[] maxZuo = new int[n];
        maxZuo[0] = height[0];
        int[] maxYou = new int[n];
        maxYou[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            maxZuo[i] = Math.max(height[i], maxZuo[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            maxYou[i] = Math.max(height[i], maxYou[i + 1]);
        }
        for (int i = 1; i < n; i++) {
            ans += Math.max(0, Math.min(maxZuo[i], maxYou[i]) - height[i]);
        }
        System.out.println(Arrays.toString(maxZuo));
        System.out.println(Arrays.toString(maxYou));
        return ans;
    }

    //双指针
    public int trap3(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(solution.trap2(height));
    }
}
